# coding:utf-8
# 编写递归函数有两个要点：
#
# 1. 出口条件，可以不止一个
# 2. 推导方法（已知上一个结果怎么推导当前结果）

# 题目：斐波那切数列是 1 1 2 3 5 8 …这样的序列。前两个数为1，后面的数为前两个数之和。
# 出口：n <= 2，返回1
# 推导：(n-1)层的结果 + (n-2)层的结果
# 代码如下：

def fib(n):
    if n<=2:
        return 1
    return fib(n-2) + fib(n-1)

resutl = fib(5) # 算出斐波那契数列第5个数
print(resutl)